# LeetCode 1081.不同字符的最小子序列
# https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters/

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        stack = []

        for index, char in enumerate(s):
            if index == 0:
                stack.append(char)
                continue
            # TODO: O(n) 可以再修改吗
            if char in stack:
                continue
            while char < stack[-1]:
                if stack[-1] in s[index + 1:]:
                    stack.pop(-1)
                else:
                    break
                if not stack:
                    break

            stack.append(char)

        return ''.join(stack)


if __name__ == '__main__':
    s = "ecbacba"
    result = Solution().smallestSubsequence(s)
    print(result)
